package com.rui.study.algorithm.P_股票_买卖股票最佳时机Ⅲ_最多两笔交易;

import java.util.Arrays;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-07 16:12
 **/
public class Temp {

    public static int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int sold = prices[prices.length - 1];
        int buy = prices[0];
        int res = 0;
        int[] before = new int[prices.length];
        int[] after = new int[prices.length];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < buy) {
                buy = prices[i];
                continue;
            }
            before[i] = prices[i] - buy;
        }
        System.out.println(Arrays.toString(before));

        int max = 0;
        for (int j = prices.length - 2; j >= 0; j--) {
            if (sold - prices[j] > max) {
                max = sold - prices[j];
            }
            after[j] = max;
            if (prices[j] > sold) {
                sold = prices[j];
                continue;
            }
        }
        System.out.println(Arrays.toString(after));

        for (int i = 0; i < prices.length; i++) {
            res = Math.max(res, after[i] + before[i]);
        }
        return res;
    }

    public static void main(String[] args) {
//        int[] prices = {3,2,6,5,0,3};
//        int[] prices = {3,2,6,5,0,3,2,6};
        int[] prices = {1,4,2,7};
//        int[] prices = {1,2,4,2,5,7,2,4,9,0};
//        int[] prices = {48,12,60,93,97,42,25,64,17,56,85,93,9,48,52,42,58,85,81,84,69,36,1,54,23,15,72,15,11,94};
//        int[] prices = {48,12,60,93,97,42,25,64,17,56,85,93,9,48,52,42,58,85};
        long start = System.currentTimeMillis();
        int maxProfit = Temp.maxProfit(prices);
        long end = System.currentTimeMillis();
        System.out.println("最大收益：" + maxProfit + ", 耗时：[" + (end - start) + "ms]");
    }
}
